#include "SegmentTree.h"

template<typename T>
void SegmentTreeLazyRangeAdd<T>::push_down(int left, int right, int node) {
    int mid = left + (right - left) / 2;
    if (left != right && lazy[node] != 0) {// 将懒惰标记下传到左右子节点
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
        // 更新左右子节点的值
        tree[node * 2] += lazy[node] * (mid - left + 1);
        tree[node * 2 + 1] += lazy[node] * (right - mid);
        // 清空当前节点的懒惰标记
        lazy[node] = 0;
    }
}
template<typename T>
T SegmentTreeLazyRangeAdd<T>::query_range(int query_left, int query_right, int node_left, int node_right, int node) {
    if (query_left <= node_left && node_right <= query_right) {
        return tree[node];
    }
    int mid = node_left + (node_right - node_left) / 2;
    T sum = 0;
    push_down(node_left, node_right, node); // 处理当前节点的懒惰标记
    if (query_left <= mid) {
        sum += query_range(query_left, query_right, node_left, mid, node * 2);
    }
    if (query_right > mid) {
        sum += query_range(query_left, query_right, mid + 1, node_right, node * 2 + 1);
    }
    return sum;
}
template<typename T>
void SegmentTreeLazyRangeAdd<T>::update_range(int update_left, int update_right, T value, int node_left, int node_right, int node) {
    if (update_left <= node_left && node_right <= update_right) {
        lazy[node] += value;
        tree[node] += value * (node_right - node_left + 1);
        return;
    }
    int mid = node_left + (node_right - node_left) / 2;
    push_down(node_left, node_right, node); // 处理当前节点的懒惰标记
    if (update_left <= mid) {
        update_range(update_left, update_right, value, node_left, mid, node * 2);
    }
    if (update_right > mid) {
        update_range(update_left, update_right, value, mid + 1, node_right, node * 2 + 1);
    }
    // 更新当前节点的值
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
template<typename T>
void SegmentTreeLazyRangeAdd<T>::build(int start, int end, int node) {
    if (start == end) {
        tree[node] = (*data)[start];
        return;
    }
    int mid = start + (end - start) / 2;
    build(start, mid, node * 2);
    build(mid + 1, end, node * 2 + 1);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
template<typename T>
SegmentTreeLazyRangeAdd<T>::SegmentTreeLazyRangeAdd(vector<T> &input_data) {
    n = input_data.size();
    tree_size = n * 4;
    tree.assign(tree_size, 0);
    lazy.assign(tree_size, 0);
    data = &input_data;
    last_index = n - 1;
    root = 1;
    build(0, last_index, root); // 建树
    data = nullptr; // 释放对原数组的引用
}
template<typename T>
T SegmentTreeLazyRangeAdd<T>::query_range(int left, int right) {
    return query_range(left, right, 0, last_index, root);
}
template<typename T>
void SegmentTreeLazyRangeAdd<T>::update_range(int left, int right, T value) {
    update_range(left, right, value, 0, last_index, root);
}



